
function Node(val, children) {
   this.val = val;
   this.children = children;
};


/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
  let result = [];
  if(root == null)
    return result;
    // 递归
  // function preorderNum(node) {
  //   result.push(node.val);
  //   for(let i = 0; i < node.children.length; i++) {
  //     preorderNum(node.children[i]);
  //   }
  // }
  // preorderNum(root);
  // 迭代
  let stack = [root];
  while(stack.length) {
    let node = stack[stack.length - 1];
    stack.splice(stack.length - 1, 1);
    result.push(node.val);
    for(let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
  return result;
};
